//
//  main.c
//  字符串匹配 BF 算法
//
//  Created by Shawn Li on 2020/5/13.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "math.h"
#include "time.h"

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

#define MAXSIZE 40

typedef int Status;
typedef int Itemtype;
//定义一个特殊的字符串类型，在 0 号位置存储串的长度。
typedef char String[MAXSIZE+1];



/// 使用普通字符串创建一个 String
/// @param s 创建结果
/// @param chars 普通字符串
Status stringInit(String s, char *chars){

    int len = (int)strlen(chars);
    if (len > MAXSIZE) {
        return ERROR;
    }else{
        s[0] = len;
        for (int i = 1; i <= s[0]; i++) {
            s[i] = *(chars + i - 1);
        }
    }
    
    return SUCCESS;
}

Status stringClear(String s){
//    将串的长度置为 0 即可
    s[0] = 0;
    return SUCCESS;
}

Status stringPrint(String s){
    if (s[0] < 1) {
        return ERROR;
    }
    for (int i = 1; i <= s[0]; i++) {
        printf("%c", s[i]);
    }
    printf("\n");
    return SUCCESS;
}

/*
 1. BF 算法--暴力匹配算法
 思路：
 1.分别利用 i 和 j 遍历主串 s 和模式串 t，i 初值pos（指定的其实位置，一般都是 1，从头开始找）；j的初值为 1
 2.如果 2 个串均未到尾，则循环执行以下操作：
    * s[i] 与 t[j] 比较，若相等，i、j 均跳步，重复操作。
    * 若不想等，指针退后重新开始比较，从主串的下一个字符开始：（i = i - j + 2）,模式串从头开始 (j = 1)。
 3.跳出循环：j > t.length 说明模式串已经匹配结束，匹配成功。（res = i - t.length）；否则匹配失败，返回-1。
 
*/


int stringMatch_BF(String s, String t, int pos){
//    开始匹配的位置
    int i = pos;
    
    int j = 1;
    
//    s 和 t 都没有匹配到结束
    while (i <= s[0] && j <= t[0]) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
//            不相等，那么 i、j都需要重新定位
//            i 后退到上次开始匹配的后一位
//            i - j + 1为上次开始的位置，再加 1 即为下一位
            i = i - j + 2;
            
//            j 回退到模式串的首位
            j = 1;
            
        }
    }
    
    if (j > t[0]) {
//        匹配成功了
        return i - t[0];
    }else{
        return -1;
    }
    
}




int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    printf("字符串模式匹配!\n");

    int i,*p;
    String s1,s2;

    stringInit(s1, "abcdexewterwtewr");
    printf("s1主串为");
    stringPrint(s1);


    stringInit(s2, "xe");
    printf("s2模式串为");
    stringPrint(s2);

    i = stringMatch_BF(s1, s2, 1);
    printf("i = %d\n",i);
    
    return 0;
}
